package cn.idu.javanote.a002;


import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * 说明：解集不能包含重复的子集。
 * 示例:
 * 输入: nums = [1,2,3]
 * 输出:
 * [
 * [3],
 *   [1],
 *   [2],
 *   [1,2,3],
 *   [1,3],
 *   [2,3],
 *   [1,2],
 *   []
 * ]
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subsets
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Main {
    public static List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> arr = new ArrayList<>();
        arr.add(new ArrayList<Integer>());

        if (nums != null && nums.length > 0) {
            for (int i = 0; i < nums.length; i++) {
                List<List<Integer>> curr = new ArrayList<>();
                for (List<Integer> item : arr) {
                    List<Integer> item_new = new ArrayList<>(item);
                    item_new.add(nums[i]);
                    curr.add(item_new);
                }
                arr.addAll(curr);
            }
        }
        return arr;
    }

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> arr = new ArrayList<>();

        int length = (int) Math.pow(2, nums.length);
        int index = 0;
        while (index < length) {
            String s = Integer.toBinaryString(index);
//            System.out.println(s);
            List<Integer> out = new ArrayList<>();
            for (int i = 0; i < s.length(); i++) {

                char c = s.charAt(s.length()-i-1);
                System.out.println(c);
                if (c == '1')
                    out.add(nums[i]);
            }
            System.out.println();
            arr.add(out);
            index++;
        }

        return arr;
    }


    public static void main(String[] args) {

        System.out.println(Arrays.toString(subsets(new int[]{1, 2, 3}).toArray()));

    }
}
